package _021_10_8

import "math"

func TreeDepth2(pRoot *TreeNode) int {
	// write code here

	treeQueue := make([]*TreeNode, 0)
	treeQueue = append(treeQueue, pRoot)
	count := 0
	if pRoot == nil {
		return count
	}
	for len(treeQueue) != 0 {
		size := len(treeQueue)
		for i := 0; i < size; i++ {
			if treeQueue[i].Left != nil {
				treeQueue = append(treeQueue, treeQueue[i].Left)
			}
			if treeQueue[i].Right != nil {
				treeQueue = append(treeQueue, treeQueue[i].Right)
			}
		}
		count++
		copy(treeQueue, treeQueue[size:])
		treeQueue = treeQueue[0 : len(treeQueue)-size]
	}
	return count
}
func IsBalancedSolution(pRoot *TreeNode) bool {
	balancedTree := make([]*TreeNode, 0)
	if pRoot == nil {
		return true
	}
	balancedTree = append(balancedTree, pRoot)
	abs := math.Abs(float64(TreeDepth2(pRoot.Right)) - float64(TreeDepth2(pRoot.Left)))
	if abs > 1 {
		return false
	}
	for len(balancedTree) != 0 {
		size := len(balancedTree)
		for i := 0; i < size; i++ {
			if balancedTree[i].Left != nil {
				balancedTree = append(balancedTree, balancedTree[i].Left)
			} else {
				if balancedTree[i].Right != nil && (balancedTree[i].Right.Left != nil || balancedTree[i].Right.Right != nil) {
					return false
				}
			}

			if balancedTree[i].Right != nil {
				balancedTree = append(balancedTree, balancedTree[i].Right)
			} else {
				if balancedTree[i].Left != nil && (balancedTree[i].Left.Left != nil || balancedTree[i].Left.Right != nil) {
					return false
				}
			}
		}
		copy(balancedTree, balancedTree[size:])
		balancedTree = balancedTree[0 : len(balancedTree)-size]
	}

	return true
}
